# -*- coding: utf-8 -*-
# author: AZJ
# date: 2024/11/20
# 假如命运扼住了你的咽喉，你就去挠她的咯吱窝
from typing import List
class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        if n == 1:
            return matrix[0][0]
        dp = [[0 for _ in range(n)] for _ in range(n)]
        for i in range(n):
            for j in range(n):
                if i == 0:
                    dp[i][j] = matrix[i][j]
                    continue
                if j == 0:
                    dp[i][j] = matrix[i][j] + min(dp[i-1][j], dp[i-1][j+1])
                    continue
                if j == n-1:
                    dp[i][j] = matrix[i][j] + min(dp[i-1][j], dp[i-1][j-1])
                    continue
                dp[i][j] = matrix[i][j] + min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1])
        return min(dp[n-1])